#include "stdafx.h"
#include "MapInfoProvider.h"
#include "MapInfoClassDefinition.h"
#include "MapInfoQueryOptimizer.h"
#include "OgrFdoUtil.h"
#include "MapInfoFilterCapabilities.h"

#include "ogr_attrind.h"

#include <algorithm>
#include <functional>
#include <FdoGeometry.h>
#include <FdoSpatial.h>

#include <assert.h>

#ifdef MIN 
#undef MIN
#endif

#ifdef MAX
#undef MAX
#endif

#ifdef _WIN32
#define MIN(a,b) min(a,b)
#define MAX(a,b) max(a,b)
#else
#define MIN(a,b) std::min(a,b)
#define MAX(a,b) std::max(a,b)
#endif

MapInfoQueryOptimizer::MapInfoQueryOptimizer(MapInfoClassDefinition * pMapInfoClassDef)
{
    m_pMapInfoClass = pMapInfoClassDef;
    m_pMapInfoFile = pMapInfoClassDef->GetMapInfoFile();
    m_keyvals = FdoPropertyValueCollection::Create();
    m_idprops = pMapInfoClassDef->GetIdentityProperty();
}

MapInfoQueryOptimizer::~MapInfoQueryOptimizer()
{    
    //make sure we free the optimized filter stack
    //in case the user didn't get a copy
    for (filter_stack::iterator iter = m_filters.begin(); iter != m_filters.end(); iter++)
        (*iter)->Release();
    
    FDO_SAFE_RELEASE(m_keyvals);
    FDO_SAFE_RELEASE(m_idprops);
}


void MapInfoQueryOptimizer::Dispose()
{
    delete this;
}

//returns the result of a query execution
//A filter must be processed with this FilterExecutor in 
//order to have a valid result value
//The caller is responsible for freeing the returned recno_list and the pointer
recno_list* MapInfoQueryOptimizer::GetResult()
{
    //only one feature ID list should be left on the evaluation stack after
    //procssing a spatial query
    _ASSERT(m_retvals.size() == 1);

    recno_list* ret = m_retvals[0];

    m_retvals.clear();


    if (ret == NULL)
        return ret;

    std::sort(ret->begin(), ret->end(), std::less<long>());

    return ret;
}

//WARNING: caller responsible for calling Release() on returned FdoFilter
FdoFilter* MapInfoQueryOptimizer::GetOptimizedFilter()
{
    //only one feature ID list should be left on the evaluation stack after
    //procssing a spatial query
    _ASSERT(m_filters.size() == 1);

    FdoFilter* ret = m_filters[0];

    m_filters.clear();

    return ret;
}

void MapInfoQueryOptimizer::ProcessBinaryLogicalOperator(FdoBinaryLogicalOperator& filter)
{
    FdoPtr<FdoFilter> left = filter.GetLeftOperand();
    FdoPtr<FdoFilter> right = filter.GetRightOperand();

    //evaluate left hand side
    left->Process(this);

    //get Process() results from return value stack
    recno_list* argLeft = NULL;
    if (m_retvals.size() > 0)
    {
        argLeft = m_retvals.back();
        m_retvals.pop_back();
    }

    //get optimized left side Filter from the stack
    FdoFilter* fLeft = m_filters.back();
    m_filters.pop_back();

    //Optimize binary logic by looking at the value of the left operand and see
    //if we have to evaluate the right one also
    if ((argLeft == NULL) && filter.GetOperation() == FdoBinaryLogicalOperations_Or)
    {
        //case where we need to look at all features for sure
        m_retvals.push_back(NULL);

        //update optimized query also by pushing
        //the old filter -- it could not be optimized
        m_filters.push_back(FDO_SAFE_ADDREF(&filter));
        if( fLeft != NULL )
            fLeft->Release();

        return;
    }

    if( filter.GetOperation() == FdoBinaryLogicalOperations_And && argLeft != NULL && argLeft->size() > 0 && fLeft == NULL )
    {
        // The left side reduced the candidate list to a smaller set and optimized away the left filter
        // We only need to apply the right filter to the reduced set.
        m_filters.push_back( right.Detach() );
        m_retvals.push_back(argLeft);
        return;
    }

    //evaluate right hand side
    right->Process(this);

    recno_list* argRight = NULL;
    if (m_retvals.size() > 0)
    {
        argRight = m_retvals.back();
        m_retvals.pop_back();
    }

    //get optimized right side Filter from the stack
    FdoFilter* fRight = m_filters.back();
    m_filters.pop_back();

    switch (filter.GetOperation())
    {
    case FdoBinaryLogicalOperations_And: 

        //Note : call to recno_list_intersection will dispose of input lists
        //if they are not to be  reused
        m_retvals.push_back(recno_list_intersection(argLeft, argRight)); 
        break;
    case FdoBinaryLogicalOperations_Or : 

        //Note : call to recno_list_union will dispose of input lists
        //if they are not to be  reused
        m_retvals.push_back(recno_list_union(argLeft, argRight));
        break;
    default: 
        //will never get here
        throw FdoException::Create(L"Invalid logical operation type");break;
    }

    //see if filters were optimized away and push appropriate
    //filter on the result stack
    if ((fLeft != NULL) ^ (fRight != NULL))
    {
        //case where one side was optimized away : other side remains
        //as the resulting filter
        if (fLeft) 
            m_filters.push_back(fLeft);
        else
            m_filters.push_back(fRight);
    }
    else //both are NULL or both are not NULL
    {
        if (fLeft)
        {
            //case where both sides remain
            m_filters.push_back(FdoBinaryLogicalOperator::Create(fLeft, filter.GetOperation(), fRight));
            fLeft->Release();
            fRight->Release();
        }
        else
        {
            //case where both sides are NULL
            m_filters.push_back(NULL);
        }
    }

}

void MapInfoQueryOptimizer::ProcessUnaryLogicalOperator(FdoUnaryLogicalOperator& filter)
{
    FdoPtr<FdoFilter> right = filter.GetOperand();

    //evaluate right hand side
    right->Process(this);

    //get Process() results from return value stack
    recno_list* argRight = m_retvals.back();
    m_retvals.pop_back();

    //get optimized Filter from the stack
    //just push the old filter on the result stack...
    //NOT cannot be simply optimized
    FdoFilter* fRight = m_filters.back();
    m_filters.pop_back();
    fRight->Release();
    m_filters.push_back(FDO_SAFE_ADDREF(&filter));


    //TODO:
    //for now NOT will push ALL features on the stack (i.e. push NULL)
    //We could in theory subtract a given set of feaure IDs (that we are applying NOT to)
    //from the set of all features, but this is too painful, so we look at all features instead
    switch (filter.GetOperation())
    {
    case FdoUnaryLogicalOperations_Not:
        m_retvals.push_back(NULL); break;
    default: 
        //will never get here
        throw FdoException::Create(L"Invalid logical operation type");break;
    }

    delete argRight;

}

void MapInfoQueryOptimizer::ProcessComparisonCondition(FdoComparisonCondition& filter)
{
    //get optimized Filter from the stack
    //just push the old filter on the result stack...
    m_filters.push_back(FDO_SAFE_ADDREF(&filter));

    //here we check if the filter contains a search on key value, in which case we can
    //use the key index table to get feature record numbers.
    //Key can be comprised of several identity properties, which complicates things.
    //In this function we check if a comparison condition is done on an identity property
    //and push appropriate indicators on the stack, to be handled by ProcessBinaryLogicalOp.

    //pushing NULL on return stack means no features are excluded for this 
    //search condition -- however, this will be ignored if the caller determines
    //that in here we matched an identity property and that it is had enough 
    //information to get a particular feature record number out of the 
    //identity property collection
    m_retvals.push_back(NULL);
 
    FdoPtr<FdoExpression> left = filter.GetLeftExpression();
    FdoPtr<FdoExpression> right = filter.GetRightExpression();
    
    //This could be optimized by a struct similar to the
    //PropertyIndex used for the full property collection
    FdoIdentifier* ident = dynamic_cast<FdoIdentifier*>(left.p);
    FdoPtr<FdoDataValue> val = FDO_SAFE_ADDREF(dynamic_cast<FdoDataValue*>(right.p));

    if (ident && val && !val->IsNull())
    {
        FdoComparisonOperations oper = filter.GetOperation();
        if (wcscmp(DEFAULT_FEATURE_ID_PROPERTY_NAME, ident->GetName()) == 0)
        {
            FdoInt32Value* pIdValue = dynamic_cast<FdoInt32Value*>(val.p);
            FdoInt32 nIdValue = pIdValue->GetInt32();
            switch(oper)
            {
                case FdoComparisonOperations_EqualTo:
                    {
                        recno_list* recno = new recno_list;
                        recno->push_back(nIdValue);
                        m_retvals.pop_back();
                        m_retvals.push_back(recno);
                    }
                    break;
                //case FdoComparisonOperations_NotEqualTo:
                //    break;
                case FdoComparisonOperations_GreaterThan:
                    {
                        int nFeatureCount = m_pMapInfoFile->GetFeatureCount(TRUE);
                        recno_list* recno = new recno_list;
                        for (int j = nIdValue + 1; j <= nFeatureCount; ++j)
                            recno->push_back(j);
                        m_retvals.pop_back();
                        m_retvals.push_back(recno);
                    }
                    break;
                case FdoComparisonOperations_GreaterThanOrEqualTo:
                    {
                        int nFeatureCount = m_pMapInfoFile->GetFeatureCount(TRUE);
                        recno_list* recno = new recno_list;
                        for (int j = nIdValue; j <= nFeatureCount; ++j)
                            recno->push_back(j);
                        m_retvals.pop_back();
                        m_retvals.push_back(recno);
                    }
                    break;
                case FdoComparisonOperations_LessThan:
                    {
                        int nFeatureCount = m_pMapInfoFile->GetFeatureCount(TRUE);
                        recno_list* recno = new recno_list;
                        for (int j = 1; j < nIdValue; j++)
                            recno->push_back(j);
                        m_retvals.pop_back();
                        m_retvals.push_back(recno);
                    }
                    break;
                case FdoComparisonOperations_LessThanOrEqualTo:
                    {
                        int nFeatureCount = m_pMapInfoFile->GetFeatureCount(TRUE);
                        recno_list* recno = new recno_list;
                        for (int j = 1; j <= nIdValue; j++)
                            recno->push_back(j);
                        m_retvals.pop_back();
                        m_retvals.push_back(recno);
                    }
                    break;
                default:
                    return;
            }
        }
        else
        {
            TABFile * pTabFile = dynamic_cast<TABFile *>(m_pMapInfoFile);
            if(!pTabFile) // Only TAB file can be optimized
            {
                return;
            }

            if (oper != FdoComparisonOperations_NotEqualTo)
            {
                return;
            }
            recno_list* recno = new recno_list;

            if(SearchKey(pTabFile, ident, val, oper, recno))
            {
                m_retvals.pop_back();
                m_retvals.push_back(recno);
            }
            else
            {
                delete recno;
            }

            
        }
    }
}

void MapInfoQueryOptimizer::ProcessInCondition(FdoInCondition& filter)
{
    //get optimized Filter from the stack
    //just push the old filter on the result stack...
    m_filters.push_back(FDO_SAFE_ADDREF(&filter));

    //here we check if the in condition is on key values, in which case we can
    //use the key index table to get feature record numbers.
    
    //start by pushing NULL on return stack, meaning no features are excluded for this 
    //search condition -- however, if the values in this in condition can be 
    //mapped to record numbers, then this NULL will be replaced by the features.
    m_retvals.push_back(NULL);

    //Key can be comprised of several identity properties, which complicates things.
    //For now, don't try to optimize this case.
    if ( m_idprops->GetCount() != 1 )
        return;

    // Check if in condition is on the key property. If not then can't optimize
    FdoPtr<FdoIdentifier> ident = filter.GetPropertyName();

    FdoPtr<FdoDataPropertyDefinition> dpd = m_idprops->FindItem(ident->GetName());

    if ( !dpd )
        return;


    // Try to convert all condition values to record numbers.

    recno_list* reclist = NULL;

    FdoPtr<FdoValueExpressionCollection> values = filter.GetValues();

    if (wcscmp(DEFAULT_FEATURE_ID_PROPERTY_NAME, ident->GetName()) == 0)
    {
        reclist = new recno_list;
        for ( int i = 0; i < values->GetCount(); i++ ) 
        {
            FdoPtr<FdoValueExpression> value = values->GetItem(i);
            FdoInt32Value* pIdValue = dynamic_cast<FdoInt32Value*>(value.p);
            if (!pIdValue || pIdValue->IsNull() ) 
            {
                delete reclist;
                return;
            }
            reclist->push_back(pIdValue->GetInt32());
        }
    }
    else
    {
        TABFile * pTabFile = dynamic_cast<TABFile *>(m_pMapInfoFile);
        if(!pTabFile) // Only TAB file can be optimized
        {
            return;
        }

        reclist = new recno_list;
        for ( int i = 0; i < values->GetCount(); i++ ) 
        {
            FdoPtr<FdoExpression> exp = values->GetItem(i);
            FdoPtr<FdoDataValue> val = FDO_SAFE_ADDREF(dynamic_cast<FdoDataValue*>(exp.p));
            
            assert(val != NULL);
            if(val == NULL)
                continue;

            if(!SearchKey(pTabFile, ident, val, FdoComparisonOperations_EqualTo, reclist))
            {
                // No index available, we 'll just return
                delete reclist;
                break;
            }
        }
    }

    // Got here so can optimize in condition. Put features on the stack.

    if(reclist)
    {
        m_retvals.pop_back();
        m_retvals.push_back(reclist);
    }
}

void MapInfoQueryOptimizer::ProcessNullCondition(FdoNullCondition& filter)
{
    //cannot optimize filter away, push back on filter result stack
    m_filters.push_back(FDO_SAFE_ADDREF(&filter));

    //pushing NULL on return stack means no features are excluded for this 
    //condition
    m_retvals.push_back(NULL);


    // TODO: May be we can?
}

// FDO RFC 49 - API change to pass tolerance in evaluate spatial operations
// changes the FDO API for spatial evaluation (FdoSpatialUtility). However,
// RFC 49 doesn't consider expression engine. If using class 
// FdoExpressionEngineUtilFeatureReader to handle spatial condition, it may
// result in wrong query results because of tolerance. So this method will 
// call newly added API by RFC 49 to handle all of spatial filter and let 
// FdoExpressionEngineUtilFeatureReader handle property filter only.
void MapInfoQueryOptimizer::ProcessSpatialCondition(FdoSpatialCondition& filter)
{
    // Get supported spatial operations by MapInfo FDO provider
    FdoPtr<MapInfoFilterCapabilities> filterCapabilities = new MapInfoFilterCapabilities();
    FdoInt32 numSpatialOps = 0;
    FdoSpatialOperations* supportedSpatialOps = filterCapabilities->GetSpatialOperations( numSpatialOps );
    
    // Check whether spatial operation specified in current filter is supported.
    bool found = false;
    FdoSpatialOperations operation = filter.GetOperation();
    for ( int i =0; i < numSpatialOps && !found; i++ )
    {
        found = ( operation == supportedSpatialOps[i] );
    }
    if ( !found )
        throw FdoException::Create(FdoException::NLSGetMessage(FDO_NLSID(FDO_105_UNSUPPORTED_SPATIAL_OPERATION)));

    // Get the geometry used in the filter.
    FdoPtr<FdoExpression> expr = filter.GetGeometry();

    // Right now we only handle literal Geometry values.
    // Any other expression will cause exception.
    FdoGeometryValue* geomval = dynamic_cast<FdoGeometryValue*>(expr.p);

    if (geomval == NULL)
        throw FdoCommandException::Create(NlsMsgGetMain(FDO_NLSID(MAPINFOPROVIDER_LITERAL_GEOM_VALUES_ONLY)));

    // Get envelope of filter geometry
    FdoPtr<FdoByteArray> fgf = geomval->GetGeometry();
    FdoPtr<FdoFgfGeometryFactory> gf = FdoFgfGeometryFactory::GetInstance();
    FdoPtr<FdoIGeometry> filterGeom = gf->CreateGeometryFromFgf(fgf);
    FdoPtr<FdoIEnvelope> filterEnvelope = filterGeom->GetEnvelope();

    // Expand a little to catch point features that lie exactly on the bounds
    double dXTolerance, dYTolerance;
    m_pMapInfoFile->GetXYTolerance(dXTolerance, dYTolerance);
    Bounds bounds;
    bounds.minx = filterEnvelope->GetMinX() - dXTolerance;
    bounds.miny = filterEnvelope->GetMinY() - dYTolerance;
    bounds.maxx = filterEnvelope->GetMaxX() + dXTolerance;
    bounds.maxy = filterEnvelope->GetMaxY() + dYTolerance;

    // Can't optimize MID/MIF files
    bool optimized = false;
    TABFile * pTabFile = dynamic_cast<TABFile *>(m_pMapInfoFile);
    if(pTabFile != NULL)
    {
        // For EnvelopeIntersects filter, we can search it via R-Tree
        if (operation == FdoSpatialOperations_EnvelopeIntersects )
        {
            // If the given geometry is axis-aligned, we can perform an R-Tree search
            if (IsAxisAlignedRectangle(filterGeom, dXTolerance, dYTolerance))
            {
                // if the bounds is bigger than the whole extent of all features,
                // we don't bother evaluating this filter
                //double minx, miny, maxx, maxy;
                OGREnvelope extent;
                pTabFile->GetExtent(&extent, true);
                if( bounds.minx <= extent.MinX &&
                    bounds.miny <= extent.MinY &&
                    bounds.maxx >= extent.MaxX &&
                    bounds.maxy >= extent.MaxY  )
                {
                    m_retvals.push_back(NULL);
                    m_filters.push_back(NULL);
                }
                else
                {
                    recno_list* rl = new recno_list;

                    //search the R-Tree for records whose bounds overlap
                    //the given IEnvelope
                    long* temp = pTabFile->FindObject(bounds.minx, bounds.miny, bounds.maxx, bounds.maxy);
                    OgrFdoUtil::ArrayToVector(temp, rl);
                    m_retvals.push_back(rl);
                    CPLFree(temp);

                    //optimize away this filter, since the R-Tree handled it
                    m_filters.push_back(NULL);
                }
                optimized = true;
            }
            // If the geometry is not a rectangle aligned with the axis, in some cases we can still 
            // narrow down the candidate result set
            else 
            {
                recno_list* rl = new recno_list;
                // Search the R-Tree for records whose bounds overlap the given IEnvelope

                long* temp = pTabFile->FindObject(bounds.minx, bounds.miny, bounds.maxx, bounds.maxy);
                OgrFdoUtil::ArrayToVector(temp, rl);
                CPLFree(temp);

                recno_list* new_rl = DoSecondaryFilter(filterGeom, operation, rl);
                delete rl;

                m_retvals.push_back(new_rl);
                m_filters.push_back(NULL);
                optimized = true;
            }
        }
        //for Intersects and Contains/Within we will narrow down the return set
        //by returning only features whose bounding boxes intersect with the 
        //bounding box of the input. The actual query result is guaranteed
        //to be a subset of the R-Tree search.
        else if ( operation == FdoSpatialOperations_Intersects 
            || operation == FdoSpatialOperations_Contains
            || operation == FdoSpatialOperations_Within
            || operation == FdoSpatialOperations_Inside
            || operation == FdoSpatialOperations_Crosses )
        {
            FdoPtr<FdoFgfGeometryFactory> gf = FdoFgfGeometryFactory::GetInstance();
            FdoPtr<FdoIGeometry> fgfgeom = gf->CreateGeometryFromFgf(fgf);

            Bounds bounds;
            FdoSpatialUtility::GetExtents(fgf, bounds.minx, bounds.miny, bounds.maxx, bounds.maxy);

            recno_list* rl = new recno_list;
            if (bounds.maxx >= bounds.minx && bounds.maxy >= bounds.miny )
            {
                //expand a little to catch point features that lie exactly on the bounds
                bounds.minx - dXTolerance, 
                bounds.miny - dYTolerance, 
                bounds.maxx + dXTolerance, 
                bounds.maxy + dYTolerance;

                //search the R-Tree for records whose bounds overlap
                //the given IEnvelope
                long* temp = pTabFile->FindObject(bounds.minx, bounds.miny, bounds.maxx, bounds.maxy);
                OgrFdoUtil::ArrayToVector(temp, rl);
                CPLFree(temp);

                recno_list* new_rl = DoSecondaryFilter(filterGeom, operation, rl);

                //push the matched feature record numbers on the result stack
                delete rl;
                rl = new_rl;
            }
            m_retvals.push_back(rl);
            m_filters.push_back(NULL);
            optimized = true;
        }
    }

    if (!optimized)
    {
        recno_list* rl = DoSecondaryFilter(filterGeom, operation, NULL);
        m_retvals.push_back(rl);
        m_filters.push_back(NULL);
    }
}

void MapInfoQueryOptimizer::ProcessDistanceCondition(FdoDistanceCondition& filter)
{
    //cannot optimize filter away, push back on filter result stack
    m_filters.push_back(FDO_SAFE_ADDREF(&filter));

    //pushing NULL on return stack means no features are excluded for this 
    //condition
    m_retvals.push_back(NULL);
}





//--------------------------------------------------------------------
// FdoIExpressionProcessor
//--------------------------------------------------------------------


void MapInfoQueryOptimizer::ProcessBinaryExpression(FdoBinaryExpression& expr)
{
}

void MapInfoQueryOptimizer::ProcessUnaryExpression(FdoUnaryExpression& expr)
{
}

void MapInfoQueryOptimizer::ProcessFunction(FdoFunction& expr)
{
}

void MapInfoQueryOptimizer::ProcessIdentifier(FdoIdentifier& expr)
{
}

void MapInfoQueryOptimizer::ProcessParameter(FdoParameter& expr)
{
}

void MapInfoQueryOptimizer::ProcessBooleanValue(FdoBooleanValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessByteValue(FdoByteValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessDateTimeValue(FdoDateTimeValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessDecimalValue(FdoDecimalValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessDoubleValue(FdoDoubleValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessInt16Value(FdoInt16Value& expr)
{
}

void MapInfoQueryOptimizer::ProcessInt32Value(FdoInt32Value& expr)
{
}

void MapInfoQueryOptimizer::ProcessInt64Value(FdoInt64Value& expr)
{
}

void MapInfoQueryOptimizer::ProcessSingleValue(FdoSingleValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessStringValue(FdoStringValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessBLOBValue(FdoBLOBValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessCLOBValue(FdoCLOBValue& expr)
{
}

void MapInfoQueryOptimizer::ProcessGeometryValue(FdoGeometryValue& expr)
{
    _ASSERT(false);
    //will not get here, identity properties are all DataProperties
}

recno_list* MapInfoQueryOptimizer::DoSecondaryFilter(FdoIGeometry *filterGeom, FdoSpatialOperations spatialOp, recno_list* res)
{
    // FDO doesn't support different XTolerance and YTolerance.
    // So let us use the smaller tolerance.
    double dXTolerance, dYTolerance, dXYTolerance;
    m_pMapInfoFile->GetXYTolerance(dXTolerance, dYTolerance);
    dXYTolerance = dXTolerance;
    if (dYTolerance < dXTolerance)
        dXYTolerance = dYTolerance;

    recno_list* newres = new recno_list();
    if (NULL == res)
    {
        int nCount = m_pMapInfoFile->GetFeatureCount(true);
        for (int i = 0; i < nCount; ++i)
        {
            OGRFeature* ogrFeature = m_pMapInfoFile->GetFeature(i);
            if (ogrFeature)
            {
                OGRGeometry* orgGeom = ogrFeature->GetGeometryRef();
                FdoPtr<FdoIGeometry> fdoGeom = OgrFdoUtil::OGRGeometryToFdoGeometry(orgGeom);

                bool  ret = FdoSpatialUtility::Evaluate( fdoGeom, spatialOp, filterGeom, dXYTolerance);
                if ( ret )
                    newres->push_back(i);

                OGRFeature::DestroyFeature(ogrFeature);
            }
        }
    }
    else
    {
        // Sort feature id list for better performance to call IMapInfoFile::GetFeature()
        std::sort(res->begin(), res->end(), std::less<long>());

        newres->reserve(res->size());
        for ( recno_list::const_iterator iter = res->begin(); iter != res->end(); iter++ )
        {
            OGRFeature* ogrFeature = m_pMapInfoFile->GetFeature(*iter);
            if (ogrFeature)
            {
                OGRGeometry* orgGeom = ogrFeature->GetGeometryRef();
                FdoPtr<FdoIGeometry> fdoGeom = OgrFdoUtil::OGRGeometryToFdoGeometry(orgGeom);

                bool ret = FdoSpatialUtility::Evaluate( fdoGeom, spatialOp, filterGeom, dXYTolerance);
                if (ret)
                    newres->push_back(*iter);

                OGRFeature::DestroyFeature(ogrFeature);
            }
        }
    }
    return newres;
}

recno_list* MapInfoQueryOptimizer::GetAllMatchesVector(OGRAttrIndex* pAttrIndex, OGRField *psKey )
{
    recno_list* results = new recno_list;
    long* temp = pAttrIndex->GetAllMatches(psKey);
    if ( NULL != temp)
    {
        int idx = 0;
        while(temp[idx] != OGRNullFID)
        {
            results->push_back(temp[idx]);
            idx++;
        }
    }

    return results;
}

//tries to obtain a feature record number from a given collection 
//of features -- used when checking if a query contains 
//filters on feature key values
recno_list* MapInfoQueryOptimizer::RecnoFromKey(FdoPropertyValueCollection* keyvals)
{
    TABFile * pTabFile = dynamic_cast<TABFile *>(m_pMapInfoFile);
    if(!pTabFile)
        return NULL;

    OGRLayerAttrIndex* layerIndex = pTabFile->GetIndex();
    if (NULL == layerIndex)
        return NULL;

    if ( !keyvals ) 
        keyvals = m_keyvals;

    try 
    {
        recno_list* result(NULL);
        FdoInt32 nValueCount = keyvals->GetCount();
        for (FdoInt32 i = 0; i < nValueCount; ++i)
        {
            FdoPtr<FdoPropertyValue> propValue = keyvals->GetItem(i);
            FdoPtr<FdoValueExpression> expression = propValue->GetValue();
            FdoDataValue* dataValue = (FdoDataValue*)(expression.p);
            OGRField* ogrValue = OgrFdoUtil::FdoDataValue2OGRField(dataValue);

            OGRAttrIndex* propIndex = layerIndex->GetFieldIndex(i);
            if (NULL == result)
                result = GetAllMatchesVector(propIndex, ogrValue);
            else
            {
                recno_list* temp1 = GetAllMatchesVector(propIndex, ogrValue);
                recno_list* temp2 = recno_list_intersection(temp1, result);
                delete temp1;
                delete result;
                result = temp2;
            }
        }

        return result;
    }
    catch (FdoException* e)
    {
        e->Release();
    }
    
    //return empty list, meaning no feature was found that matches the 
    //given key. This will prevent the feature reader from looping over
    //features (like it would if we returned NULL instead of empty list)
    return new recno_list;
}

bool MapInfoQueryOptimizer::SearchKey(TABFile *pTabFile, FdoIdentifier * ident, FdoDataValue * val, FdoComparisonOperations oper, recno_list* recno)
{
    int index = m_pMapInfoClass->GetPropertyIndex(ident->GetName());
    if(index)
    {
        GByte * pKey = m_pMapInfoClass->GenerateIndexKey(index, val);
        if(! pKey)
        {
            return false;
        }
        int keyLen = m_pMapInfoClass->GetKeyLength(index);
        GByte * key = (GByte*)alloca(keyLen);
        memcpy(key, pKey, keyLen);

        TABINDFile * pINDFile = pTabFile->GetINDFileRef();
        switch(oper)
        {
        case FdoComparisonOperations_EqualTo:
            {
                GInt32 feat = pINDFile->FindFirst(index, key, Equal);
                while(feat)
                {
                    recno->push_back(feat);
                    feat = pINDFile->FindNext(index, key, Equal);
                }  
            }
            break;
            //case FdoComparisonOperations_NotEqualTo:
            //    break;
        case FdoComparisonOperations_GreaterThan:
            {
                GInt32 feat = pINDFile->FindFirst(index, key, Greater);
                while(feat)
                {
                    recno->push_back(feat);
                    feat = pINDFile->FindNext(index, key, Greater);
                }  
            }
            break;
        case FdoComparisonOperations_GreaterThanOrEqualTo:
            {
                GInt32 feat = pINDFile->FindFirst(index, key, GreaterEqual);
                while(feat)
                {
                    recno->push_back(feat);
                    feat = pINDFile->FindNext(index, key, GreaterEqual);
                }  
            }
            break;
        case FdoComparisonOperations_LessThan:
            {
                GInt32 feat = pINDFile->FindFirst(index, key, Less);
                while(feat)
                {
                    recno->push_back(feat);
                    feat = pINDFile->FindNext(index, key, Less);
                }  
            }
            break;
        case FdoComparisonOperations_LessThanOrEqualTo:
            {
                GInt32 feat = pINDFile->FindFirst(index, key, LessEqual);
                while(feat)
                {
                    recno->push_back(feat);
                    feat = pINDFile->FindNext(index, key, LessEqual);
                }  
            }
            break;
        default:
            return false;
        }

        return true;
    }

    return false;

    
}

recno_list* MapInfoQueryOptimizer::recno_list_union(recno_list* left, recno_list* right)
{
    //if one of the lists is null it means it iterates over all features...
    //so return that list as the union of the two
    if (left == NULL)
        return left;

    if (right == NULL)
        return right;

    std::sort(left->begin(), left->end(), std::less<long>());
    std::sort(right->begin(), right->end(), std::less<long>());

    recno_list::iterator iter1 = left->begin();
    recno_list::iterator iter2 = right->begin();

    recno_list* ret = new recno_list;

    while (iter1 != left->end() || iter2 != right->end())
    {
        if (iter1 == left->end())
            ret->push_back(*iter2++);
        else if (iter2 == right->end())
            ret->push_back(*iter1++);
        else if (*iter2 < *iter1)
            ret->push_back(*iter2++);
        else if (*iter2 > *iter1)
            ret->push_back(*iter1++);
        else
        {
            ret->push_back(*iter1);
            iter1++;
            iter2++;
        }
    }

    //dispose of inputs and return newly allocated list
    delete left;
    delete right;

    return ret;
}

recno_list* MapInfoQueryOptimizer::recno_list_intersection(recno_list* left, recno_list* right)
{
    //if one of the lists is null it means it iterates over all features...
    //so return the non-null list as the intersection of the two, if one is non-null
    if (left == NULL)
        return right;

    if (right == NULL)
        return left;

    std::sort(left->begin(), left->end(), std::less<long>());
    std::sort(right->begin(), right->end(), std::less<long>());

    recno_list::iterator iter1 = left->begin();
    recno_list::iterator iter2 = right->begin();

    recno_list* ret = new recno_list;

    while(iter1 != left->end() || iter2 != right->end())
    {
        if (iter1 == left->end())
            return ret;
        else if (iter2 == right->end())
            return ret;
        else if (*iter2 < *iter1)
            iter2++;
        else if (*iter2 > *iter1)
            iter1++;
        else
        {
            ret->push_back(*iter1);
            iter1++;
            iter2++;
        }
    }

    //dispose of inputs and return newly allocated list
    delete left;
    delete right;

    return ret;
}


//determines whether the given FGF stream is an axis-aligned rectangle
//which can be used for R-Tree searches
bool MapInfoQueryOptimizer::IsAxisAlignedRectangle(FdoIGeometry* geom, double xTolerance, double yTolerance)
{
    //TODO
    //TODO
    //TODO
    //Check if all this is fast with the new faster FDO geometry

    FdoIPolygon* box = NULL;
    if( geom->GetDerivedType() == FdoGeometryType_Polygon )
        box = (FdoIPolygon*)(geom);

    //it has to be a polygon
    if (box == NULL)
        return false;

    if (box->GetInteriorRingCount() > 0)
        return false;

    FdoPtr<FdoILinearRing> outer = box->GetExteriorRing();

    //technically the ring must always be closed so it will have 5 points
    //but let's be nicer and check if it is a rectangle even if the user 
    //didn't bother to close it.
    if (outer->GetCount() < 4 || outer->GetCount() > 5)
        return false;

    FdoPtr<FdoDirectPositionCollection> pts = outer->GetPositions();

    FdoPtr<FdoIDirectPosition> p0 = pts->GetItem(0);
    FdoPtr<FdoIDirectPosition> p1 = pts->GetItem(1);
    FdoPtr<FdoIDirectPosition> p2 = pts->GetItem(2);
    FdoPtr<FdoIDirectPosition> p3 = pts->GetItem(3);

    bool isRect = false;
    bool firstSegHorizontal = false;

    // Determine if it is axis aligned rectangle -- I know code below it's ugly!
    if (   (   AreEqual(p0->GetX(), p1->GetX(), xTolerance) //case of first segment is vertical
        && AreEqual(p1->GetY(), p2->GetY(), yTolerance) 
        && AreEqual(p2->GetX(), p3->GetX(), xTolerance)
        && AreEqual(p3->GetY(), p0->GetY(), yTolerance)  ))
    {
        isRect = true;
    }

    return true;
}

bool MapInfoQueryOptimizer::AreEqual(double/*&*/ d1, double/*&*/ d2, double tolarance)
{
    if (fabs(d1 - d2) <= tolarance)
        return true;

    return false;
}
